home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / graphic / jpegsrc4.zip / JCHUFF.C < prev    next >
C/C++ Source or Header  |  1992-07-23  |  21KB  |  704 lines
  1. /*
  2.  * jchuff.c
  3.  *
  4.  * Copyright (C) 1991, 1992, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy encoding routines.
  9.  * These routines are invoked via the methods entropy_encode,
  10.  * entropy_encode_init/term, and entropy_optimize.
  11.  */
  12.  
  13. #include "jinclude.h"
  14.  
  15.  
  16. /* Static variables to avoid passing 'round extra parameters */
  17.  
  18. static compress_info_ptr cinfo;
  19.  
  20. static INT32 huff_put_buffer;    /* current bit-accumulation buffer */
  21. static int huff_put_bits;    /* # of bits now in it */
  22.  
  23. static char * output_buffer;    /* output buffer */
  24. static int bytes_in_buffer;
  25.  
  26.  
  27.  
  28. LOCAL void
  29. fix_huff_tbl (HUFF_TBL * htbl)
  30. /* Compute derived values for a Huffman table */
  31. {
  32.   int p, i, l, lastp, si;
  33.   char huffsize[257];
  34.   UINT16 huffcode[257];
  35.   UINT16 code;
  36.   
  37.   /* Figure C.1: make table of Huffman code length for each symbol */
  38.   /* Note that this is in code-length order. */
  39.  
  40.   p = 0;
  41.   for (l = 1; l <= 16; l++) {
  42.     for (i = 1; i <= (int) htbl->bits[l]; i++)
  43.       huffsize[p++] = (char) l;
  44.   }
  45.   huffsize[p] = 0;
  46.   lastp = p;
  47.   
  48.   /* Figure C.2: generate the codes themselves */
  49.   /* Note that this is in code-length order. */
  50.   
  51.   code = 0;
  52.   si = huffsize[0];
  53.   p = 0;
  54.   while (huffsize[p]) {
  55.     while (((int) huffsize[p]) == si) {
  56.       huffcode[p++] = code;
  57.       code++;
  58.     }
  59.     code <<= 1;
  60.     si++;
  61.   }
  62.   
  63.   /* Figure C.3: generate encoding tables */
  64.   /* These are code and size indexed by symbol value */
  65.  
  66.   /* Set any codeless symbols to have code length 0;
  67.    * this allows emit_bits to detect any attempt to emit such symbols.
  68.    */
  69.   MEMZERO(htbl->ehufsi, SIZEOF(htbl->ehufsi));
  70.  
  71.   for (p = 0; p < lastp; p++) {
  72.     htbl->ehufco[htbl->huffval[p]] = huffcode[p];
  73.     htbl->ehufsi[htbl->huffval[p]] = huffsize[p];
  74.   }
  75.   
  76.   /* We don't bother to fill in the decoding tables mincode[], maxcode[], */
  77.   /* and valptr[], since they are not used for encoding. */
  78. }
  79.  
  80.  
  81. /* Outputting bytes to the file */
  82.  
  83. LOCAL void
  84. flush_bytes (void)
  85. {
  86.   if (bytes_in_buffer)
  87.     (*cinfo->methods->entropy_output) (cinfo, output_buffer, bytes_in_buffer);
  88.   bytes_in_buffer = 0;
  89. }
  90.  
  91.  
  92. #define emit_byte(val)  \
  93.   MAKESTMT( if (bytes_in_buffer >= JPEG_BUF_SIZE) \
  94.           flush_bytes(); \
  95.         output_buffer[bytes_in_buffer++] = (char) (val); )
  96.  
  97.  
  98.  
  99. /* Outputting bits to the file */
  100.  
  101. /* Only the right 24 bits of huff_put_buffer are used; the valid bits are
  102.  * left-justified in this part.  At most 16 bits can be passed to emit_bits
  103.  * in one call, and we never retain more than 7 bits in huff_put_buffer
  104.  * between calls, so 24 bits are sufficient.
  105.  */
  106.  
  107. INLINE
  108. LOCAL void
  109. emit_bits (UINT16 code, int size)
  110. {
  111.   /* This routine is heavily used, so it's worth coding tightly. */
  112.   register INT32 put_buffer = code;
  113.   register int put_bits = huff_put_bits;
  114.  
  115.   /* if size is 0, caller used an invalid Huffman table entry */
  116.   if (size == 0)
  117.     ERREXIT(cinfo->emethods, "Missing Huffman code table entry");
  118.  
  119.   put_buffer &= (((INT32) 1) << size) - 1; /* Mask off any excess bits in code */
  120.   
  121.   put_bits += size;        /* new number of bits in buffer */
  122.   
  123.   put_buffer <<= 24 - put_bits; /* align incoming bits */
  124.  
  125.   put_buffer |= huff_put_buffer; /* and merge with old buffer contents */
  126.   
  127.   while (put_bits >= 8) {
  128.     int c = (int) ((put_buffer >> 16) & 0xFF);
  129.     
  130.     emit_byte(c);
  131.     if (c == 0xFF) {        /* need to stuff a zero byte? */
  132.       emit_byte(0);
  133.     }
  134.     put_buffer <<= 8;
  135.     put_bits -= 8;
  136.   }
  137.  
  138.   huff_put_buffer = put_buffer;    /* Update global variables */
  139.   huff_put_bits = put_bits;
  140. }
  141.  
  142.  
  143. LOCAL void
  144. flush_bits (void)
  145. {
  146.   emit_bits((UINT16) 0x7F, 7);    /* fill any partial byte with ones */
  147.   huff_put_buffer = 0;        /* and reset bit-buffer to empty */
  148.   huff_put_bits = 0;
  149. }
  150.  
  151.  
  152.  
  153. /* Encode a single block's worth of coefficients */
  154. /* Note that the DC coefficient has already been converted to a difference */
  155.  
  156. LOCAL void
  157. encode_one_block (JBLOCK block, HUFF_TBL *dctbl, HUFF_TBL *actbl)
  158. {
  159.   register int temp, temp2;
  160.   register int nbits;
  161.   register int k, r, i;
  162.   
  163.   /* Encode the DC coefficient difference per section F.1.2.1 */
  164.   
  165.   temp = temp2 = block[0];
  166.  
  167.   if (temp < 0) {
  168.     temp = -temp;        /* temp is abs value of input */
  169.     /* For a negative input, want temp2 = bitwise complement of abs(input) */
  170.     /* This code assumes we are on a two's complement machine */
  171.     temp2--;
  172.   }
  173.   
  174.   /* Find the number of bits needed for the magnitude of the coefficient */
  175.   nbits = 0;
  176.   while (temp) {
  177.     nbits++;
  178.     temp >>= 1;
  179.   }
  180.   
  181.   /* Emit the Huffman-coded symbol for the number of bits */
  182.   emit_bits(dctbl->ehufco[nbits], dctbl->ehufsi[nbits]);
  183.  
  184.   /* Emit that number of bits of the value, if positive, */
  185.   /* or the complement of its magnitude, if negative. */
  186.   if (nbits)            /* emit_bits rejects calls with size 0 */
  187.     emit_bits((UINT16) temp2, nbits);
  188.   
  189.   /* Encode the AC coefficients per section F.1.2.2 */
  190.   
  191.   r = 0;            /* r = run length of zeros */
  192.   
  193.   for (k = 1; k < DCTSIZE2; k++) {
  194.     if ((temp = block[k]) == 0) {
  195.       r++;
  196.     } else {
  197.       /* if run length > 15, must emit special run-length-16 codes (0xF0) */
  198.       while (r > 15) {
  199.     emit_bits(actbl->ehufco[0xF0], actbl->ehufsi[0xF0]);
  200.     r -= 16;
  201.       }
  202.  
  203.       temp2 = temp;
  204.       if (temp < 0) {
  205.     temp = -temp;        /* temp is abs value of input */
  206.     /* This code assumes we are on a two's complement machine */
  207.     temp2--;
  208.       }
  209.       
  210.       /* Find the number of bits needed for the magnitude of the coefficient */
  211.       nbits = 1;        /* there must be at least one 1 bit */
  212.       while (temp >>= 1)
  213.     nbits++;
  214.       
  215.       /* Emit Huffman symbol for run length / number of bits */
  216.       i = (r << 4) + nbits;
  217.       emit_bits(actbl->ehufco[i], actbl->ehufsi[i]);
  218.       
  219.       /* Emit that number of bits of the value, if positive, */
  220.       /* or the complement of its magnitude, if negative. */
  221.       emit_bits((UINT16) temp2, nbits);
  222.       
  223.       r = 0;
  224.     }
  225.   }
  226.  
  227.   /* If the last coef(s) were zero, emit an end-of-block code */
  228.   if (r > 0)
  229.     emit_bits(actbl->ehufco[0], actbl->ehufsi[0]);
  230. }
  231.  
  232.  
  233.  
  234. /*
  235.  * Initialize for a Huffman-compressed scan.
  236.  * This is invoked after writing the SOS marker.
  237.  * The pipeline controller must establish the entropy_output method pointer
  238.  * before calling this routine.
  239.  */
  240.  
  241. METHODDEF void
  242. huff_init (compress_info_ptr xinfo)
  243. {
  244.   short ci;
  245.   jpeg_component_info * compptr;
  246.  
  247.   /* Initialize static variables */
  248.   cinfo = xinfo;
  249.   huff_put_buffer = 0;
  250.   huff_put_bits = 0;
  251.  
  252.   /* Initialize the output buffer */
  253.   output_buffer = (char *) (*cinfo->emethods->alloc_small)
  254.                 ((size_t) JPEG_BUF_SIZE);
  255.   bytes_in_buffer = 0;
  256.  
  257.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  258.     compptr = cinfo->cur_comp_info[ci];
  259.     /* Make sure requested tables are present */
  260.     if (cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no] == NULL ||
  261.     cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no] == NULL)
  262.       ERREXIT(cinfo->emethods, "Use of undefined Huffman table");
  263.     /* Compute derived values for Huffman tables */
  264.     /* We may do this more than once for same table, but it's not a big deal */
  265.     fix_huff_tbl(cinfo->dc_huff_tbl_ptrs[compptr->dc_tbl_no]);
  266.     fix_huff_tbl(cinfo->ac_huff_tbl_ptrs[compptr->ac_tbl_no]);
  267.     /* Initialize DC predictions to 0 */
  268.     cinfo->last_dc_val[ci] = 0;
  269.   }
  270.  
  271.   /* Initialize restart stuff */
  272.   cinfo->restarts_to_go = cinfo->restart_interval;
  273.   cinfo->next_restart_num = 0;
  274. }
  275.  
  276.  
  277. /*
  278.  * Emit a restart marker & resynchronize predictions.
  279.  */
  280.  
  281. LOCAL void
  282. emit_restart (compress_info_ptr cinfo)
  283. {
  284.   short ci;
  285.  
  286.   flush_bits();
  287.  
  288.   emit_byte(0xFF);
  289.   emit_byte(RST0 + cinfo->next_restart_num);
  290.  
  291.   /* Re-initialize DC predictions to 0 */
  292.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  293.     cinfo->last_dc_val[ci] = 0;
  294.  
  295.   /* Update restart state */
  296.   cinfo->restarts_to_go = cinfo->restart_interval;
  297.   cinfo->next_restart_num++;
  298.   cinfo->next_